package binaryTree;

import org.junit.Test;

import java.util.HashMap;
import java.util.LinkedList;

//二叉树的最近公共祖先
public class LeetCode_236 {

    //定义二叉树节点
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return solution_1(root,p,q);
    }

    /**
    * @Description: 递归，分情况讨论
    * @Author: kunkun
    * @Date:  2025/3/13 10:50
    * @Parameters:
    * @Return
    * @Throws
    */
    private TreeNode solution_1(TreeNode root, TreeNode p, TreeNode q) {
        //1. 递归返回条件
        if (root==p||root==q){
            return root;
        }
        if (root==null){
            return null;
        }
        if (root.left==null&&root.right==null){
            return null;
        }
        //2. 递归左右子树
        TreeNode leftNode = solution_1(root.left,p,q);
        TreeNode rightNode = solution_1(root.right,p,q);

        //3. 返回
        if (leftNode==null && rightNode==null){
            return null;
        } else if (leftNode!=null && rightNode==null) {
            return leftNode;
        } else if (leftNode==null && rightNode!=null) {
            return rightNode;
        }else {
            return root;
        }


    }


}
